Матч 63, Рассказывание историй (Telltale)

 

Ваш друг любит рассказывать историю: в правдивой и в преувеличенной форме. В преувеличенной форме рассказ звучит интереснее, но друг не хочет быть пойманным на лжи. Некоторые люди знают правдивую историю. Поэтому на вечеринках с их присутствием следует говорить правду. Также известно, что если некто услышит обе версии истории, то он уличит друга во лжи.

Всего имеется n людей, пронумерованных от 1 до n. Люди, которые знают правдивую версию истории, находятся в массиве а. Ячейка parties[i] содержит список людей, присутствующих на i - ой вечеринке. Необходимо найти наибольшее количество вечеринок, на которых можно рассказать историю в преувеличенной форме и при этом не быть пойманным на лжи.

 

Класс: Telltale

Метод: int doNotTellTheTruth(int n, vector<int> a,

                                    vector<string> parties)

Ограничения: 1 £ n £ 50, a содержит от 0 до n различных элементов, parties содержит от 1 до 50 строк, каждая из которых содержит от 1 до 50 символов.

 

Вход. Количество людей n, массив а, содержащий номера людей, знающих правдивую историю, а также массив parties, описывающий присутствующих людей на всех вечеринках.

 

Выход. Наибольшее количество вечеринок, на которых можно рассказать историю в преувеличенной форме и при этом не быть пойманным на лжи.

 

Пример входа

n

a

parties

4

{}

{"1 2", "3", "2 3 4"}

4

{1}

{"1", "2", "3", "4", "4 1"}

8

{1, 2, 7}

{"3 4", "5", "5 6", "6 8", "8"}

10

{1, 2, 3, 4}

{"1 5", "2 6", "7", "8", "7 8", "9", "10", "3 10", "4"}

 

Пример выхода

3

2

5

4

 

 

РЕШЕНИЕ

алгоритм Флойда - Уоршела

 

Информацию о вечеринках занесем в массив p: p[i][j] содержит 1, если на i - ой вечеринке присутствует j - ый человек и 0 иначе. Если j - ый и k - ый человек присутствовали на i - ой вечеринке, то они вместе должны слышать или правдивый, или преувеличенный вариант истории. Этот факт отметим присвоением m[j][k] = m[k][j] = 1.

Люди пронумерованы числами от 1 до n. Введем фиктивного нулевого человека, который слышал правдивую историю. Тогда для каждого i - ого человека, присутствующего в массиве а, положим m[0][i] = 1 (i - ый человек слышал правдивую историю). Запустим на массиве m алгоритм транзитивного замыкания графа (вариант алгоритма Флойда – Уоршела). После его завершения m[i][j] содержит 1, если i - ый и j - ый человек обязаны слышать либо правдивый, или преувеличенный вариант истории (при этом  i - ый и j - ый человек не обязательно встречались на одной вечеринке). Тогда если ячейка m[0][i] содержит 1, то на вечеринке, где присутствует i - ый человек, рассказ должен звучать правдиво.

Перебираем все вечеринки и подсчитываем те из них, на которых нет ни одного человека, для которого история должна звучать правдиво.

 

ПРОГРАММА

 

#include <cstdio>

#include <vector>

#include <string>

#include <memory>

#include <sstream>

#define MAX 51

using namespace std;

 

int p[MAX][MAX],m[MAX][MAX];

 

class Telltale

{

public:

  int doNotTellTheTruth(int n, vector<int> a, vector<string> parties)

  {

    int i, j, k, s, num, res, sz = parties.size();

    memset(p,0,sizeof(p)); memset(m,0,sizeof(m));

    for(i = 0; i < sz; i++)

    {

      stringstream s(parties[i]);

      while(s >> num) p[i][num] = 1;

      m[i][i] = 1;

    }

 

    for(i = 0; i < sz; i++) for(j = 1; j <= n; j++) for(k = 1; k <= n; k++)

      if (p[i][j] && p[i][k]) m[j][k] = m[k][j] = 1;

 

    for(i = 0; i < a.size(); i++) m[0][a[i]] = 1;

    for(k = 0; k <= n; k++) for(i = 0; i <= n; i++) for(j = 0; j <= n; j++)

      if (m[i][k] && m[k][j]) m[i][j] = 1;

 

    for(res = i = 0; i < sz; i++)

    {

      for(s = 0, j = 1; j <= n; j++)

        s += p[i][j] * m[0][j];

      if (!s) res++;

    }

    return res;

  }

};